// 实现一个叫做链表的类型
#include <iostream>
using namespace std;

class Node {
public:
  int value; // 节点里存储值是什么
  Node *next; // 下一个节点在哪

  Node(int v, Node *p) {
    value = v;
    next = p;
  }
};

// LinkList l;
// 单向链表
class LinkList {
public:
  Node *head;
  int size;

  LinkList() {
    head = nullptr;
    size = 0;
  }

  // 打印链表里的所有元素
  void print() {
    Node *current = head;

    while (current != nullptr) {
      cout << current->value << " ";
      current = current->next;
    }

    cout << endl;
  }

  // 向链表中添加元素
  // LinkList ll;
  // ll.addAtIndex(0, 11);
  // 11 -> nullptr
  // ll.addAtIndex(1, 12);
  // 11 -> 12 -> nullptr
  // ll.addAtIndex(2, 13);
  // 11 -> 12 -> 13 -> nullptr
  void addAtIndex(int pos, int v) {
    // 1. 判断 pos 是否合法
    if (pos < 0 || pos > size) {
      cout << "Invalid pos: " << pos << endl;
      return;
    }

    // 2. 用 v 创建一个 Node
    Node *toAdd = new Node(v, nullptr);

    // 3. 把 toAdd 添加到链表
    ++size;

    if (head == nullptr) {
      // 现在，链表里一个元素都还没有呢
      // 用刚才创建出来的这个新的节点当作表头
      head = toAdd;
    }
    else {
      // 我们必须要 pos 位置的前一个节点的位置
      Node *curr = head;
      int i = 0; // 记录我们往前走了多少步

      while (i < pos - 1) {
        curr = curr->next;
        ++i;
      }

      // 此时，curr 就指向了插入位置的前一个位置
      toAdd->next = curr->next;
      curr->next = toAdd;
    }
  }
  
  // 11 -> 12 -> 13
  // addAtTail(14)
  // 11 -> 12 -> 13 -> 14
  // addAtTail(15)
  // 11 -> 12 -> 13 -> 14 -> 15
  void addAtTail(int v) {
    addAtIndex(size, v);
  }

  void addAtHead(int v) {
    addAtIndex(0, v);
  }

  // 以 head 起始的链表是否存在循环
  bool hasCycle() {
    if (head == nullptr) {
      return false;
    }

    Node *turtle = head;
    Node *rabbit = turtle->next;

    while (true) {
      if (turtle == rabbit) {
        return true;
      }
      else if (rabbit == nullptr) {
        return false;
      }

      turtle = turtle->next;
      rabbit = rabbit->next;

      if (rabbit == nullptr) {
        return false;
      } 

      rabbit = rabbit->next;
    }
  }

  // 返回索引 idx 位置的节点指针
  // 从 head 开始的 idx 个 next
  Node *getNode(int idx) {
    Node *p = head;
    int i = 0;

    while (i < idx) {
      p = p->next;
      ++i;
    }

    return p;
  }

  // 删除链表中位置 pos 的元素
  void deleteAtIndex(int pos) {
    if (pos == 0) {
      Node *toDelete = head;
      head = head->next;
      delete toDelete;
    }
    {
      Node *toDelete = getNode(pos);
      Node *prev = getNode(pos - 1);

      prev->next = toDelete->next;
      delete toDelete;
    }
    
  }

  // head
  // 1 -> 2 -> 3 -> 4 -> 5 -> nullptr
  // 
  // Node *p -> nullptr
  // 5 -> 4 -> 3 -> 2 -> 1
  // head
  void reverse() {
    Node *p = head;
    Node *newHead = nullptr;

    while (p != nullptr) {
      // 遍历链表中的每一个元素
      Node *newNode = new Node(p->value, nullptr);

      if (newHead == nullptr) {
        newHead = newNode;
      }
      else {
        newNode->next = newHead;
        newHead = newNode;
      }

      p = p->next;
    }

    // 当我们给 head 赋值之前，我们要先删掉原来 head 指向的所有节点
    
    clear();

    head = newHead;
  }

  // 清空链表的所有节点
  // h->next
  // Node * p= head->next;
  //  p
  //  h
  //  nullptr
  void clear() {
    while (head != nullptr) {
      deleteAtIndex(0);
    }
  }

  void oddEvenLinkList() {
    
  }

  /**
  Palindrome - 回文
            1 -> 2 -> 3 -> nullptr
  vp        vq
  1 -> 2 -> 3 -> 2 -> 1 -> nullptr 
                           ^F
  当我们使用这种快慢指针的方式遍历链表的时候，当快指针指向表尾的时候，慢指针正好指向链表的中心元素
            1 -> 2 -> nullptr
  vh        vS
  1 -> 2 -> 2 -> 1 -> nullptr
                      ^F

  1 -> 2 -> 2 -> 1 -> nullptr

  1 -> 2 -> 3 -> nullptr X

  LinkList ll;
  ll.addAtTail(1);
  ll.addAtTail(2);
  ll.addAtTail(2);
  ll.addAtTail(1);
  ll.isPalindrome(); True

  思路1: 遍历链表，把每一个数字都存到一个 vector 里，之后利用 vector 不断比较头尾元素。

  思路2:
  */
  bool isPalindrome() {
    // 1. 用快慢指针的方法，找到链表的中心位置
    Node *s = head;
    Node *f = head->next;

    while (f != nullptr) {
      s = s->next;
      f = f->next;

      if (f == nullptr) {
        break;
      }

      f = f->next;
    }

    // s 就是中心位置
    cout << "s.value = "<< s->value << endl;

    // 要以 s 作为开始，把 s 后面一段链表整个逆序过来。
    Node *originHead = head;
    head = s;
    reverse();

    // originHead - 整个链表的表头
    // head - 逆序之后后半段的表头

    Node *p = originHead;
    Node *q = head;

    while (q != nullptr) {
      if (p->value != q->value) {
        reverse();
        head = originHead;
        return false;
      }

      p = p->next;
      q = q->next;
    }

    reverse();
    head = originHead;
    return true;
  }
};

